<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>longestAB</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
        
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        <style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="longestab">longestAB</h1>
<h1 id="1-1443-longest-ab-substring-lintcode">1. 1443. Longest AB Substring     lintcode</h1>
<p><a href="https://www.lintcode.com/problem/longest-ab-substring/description">https://www.lintcode.com/problem/longest-ab-substring/description</a></p>
<pre><code>Description
中文English
Given a string s of only 'A' and 'B', find the longest substring that satisfies the number of 'A' and 'B' are the same. Please output the   length of this substring.
This substring can be empty.
n is the length of s, 2&lt;=n&lt;=1000000.
Have you met this question in a real interview?  Yes
Problem Correction
Example
Example1
Input: s = &quot;ABAAABBBA&quot;
Output: 8
Explanation: 
Substring s[0,7] and s[1,8] meet the conditions, their length is 8.

Example2
Input: s = &quot;AAAAAA&quot;
Output: 0
Explanation: 
No substring satisfies the condition except empty substring.
</code></pre>
<h2 id="11-本题来自lintcode-暴力解法on3不难想到">1.1 本题来自lintcode, 暴力解法O(n^3)不难想到</h2>
<pre><code><code><div>class Solution {
public:
    /**
     * @param S: a String consists of a and b
     * @return: the longest of the longest string that meets the condition
     */
    int getAns(string &amp;S) {
        // Write your code here
        int maxsum=0;
        for(int j=0;j&lt;S.length();j++){
            int asum=0;
            int bsum=0;
            for(int i=j;i&lt;S.length();i++){
                if(S[i]=='A') asum++;
                else if(S[i]=='B') bsum++;
                if(asum==bsum&amp;&amp;asum+bsum&gt;maxsum) maxsum=asum+bsum;
            }
        }
        return maxsum;
    }
</div></code></code></pre>
<h2 id="12-下面是on的解法">1.2 下面是O(n)的解法。</h2>
<p>我们先遍历整个数组一次， 以matrix[i]代表 s[0]~s[i]范围内 (A字符出现数目 - B字符出现数目)的值。
那么针对某个差值k,  我们知道k出现的最大处， 和-k出现的最小处。 两者的距离就是我们要判断。
例如假设 s[0:17] 这个字符串 A出现的次数比B 多3，   s[0:5]这个字符串A出现的次数比B少3.  那么17-5=12 就正好是两者相等的一个情况。</p>
<pre><code><code><div>class Solution {
public:
    /*
     * @param S: a String consists of a and b
     * @return: the longest of the longest string that meets the condition
     */
    int getAns(string &amp;s) {
        // write your code here
        int n = s.length(), i;
        
        vector&lt;int&gt; dpmax(2*n+1,0);
        vector&lt;int&gt; dpmin(2*n+1,INT_MAX);
        
        dpmin[n] = 0;
        int sum = 0;
        for(i = 0; i &lt; n; i++) {
            if(s[i] == 'A') {
                sum++;
            } else {
                sum--;
            }
            dpmax[sum + n] = max(dpmax[sum + n], i + 1);
            dpmin[sum + n] = min(dpmin[sum + n], i + 1);
        }
        int ans = 0;
        for(i = -n; i &lt;= n; i++) {
            ans = max(ans, dpmax[i + n] - dpmin[n + i]);
        }
        return ans;
    }
</div></code></code></pre>
<h2 id="13-本题可以扩展一下如果是求longest-abc-substring">1.3 本题可以扩展一下，如果是求Longest ABC Substring</h2>
<pre><code><code><div>其实解法也一样，只是一定要用哈希表了，不能用数组了。
a b c a b c a
1 0 0 1 0 0 1     # a相对于b的次数
1 1 0 1 1 0 1     # a相对于c的次数

{
  (1,1) : [min,max]
  (0,1) : [min, max]
}
</div></code></code></pre>
<h1 id="2-力扣-1248-统计优美子数组">2. 力扣 1248. 统计「优美子数组」</h1>
<ul>
<li><a href="https://zhuanlan.zhihu.com/p/143731475">https://zhuanlan.zhihu.com/p/143731475</a></li>
<li><a href="https://leetcode.com/problems/count-number-of-nice-subarrays/">https://leetcode.com/problems/count-number-of-nice-subarrays/</a></li>
</ul>
<p>题目描述</p>
<pre><code><code><div>给你一个整数数组 nums 和一个整数 k。

如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

示例 1:
输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2:

输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。
示例 3:

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16
数据范围

1 &lt;= nums.length &lt;= 50000
1 &lt;= nums[i] &lt;= 10^5
1 &lt;= k &lt;= nums.length
</div></code></code></pre>
<h2 id="21-on解法">2.1 O(n)解法</h2>
<p>仔细观察题干，可以发现本题有两大关键特征：</p>
<ol>
<li>连续子数组</li>
<li>子数组内恰好有 k 个奇数数字</li>
</ol>
<p>如果对「前缀和」算法有所掌握的话，凭借这两大特征不难确定此题可以用「前缀和」求解。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">numberOfSubarrays</span><span class="hljs-params">(self, nums: List[int], k: int)</span> -&gt; int:</span>
        ans = <span class="hljs-number">0</span>
        level = <span class="hljs-number">0</span>
        levels = [<span class="hljs-number">1</span>] + [<span class="hljs-number">0</span>] * len(nums)  <span class="hljs-comment"># 注意 levels[0]必须为1</span>
        <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums:
            <span class="hljs-keyword">if</span> num % <span class="hljs-number">2</span> != <span class="hljs-number">0</span>:
                level += <span class="hljs-number">1</span>
            levels[level] += <span class="hljs-number">1</span>
            <span class="hljs-keyword">if</span> level &gt;= k:
                ans += levels[level-k]
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<h2 id="22-另一种-on-解法">2.2 另一种 O(n) 解法</h2>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">numberOfSubarrays</span><span class="hljs-params">(self, nums: List[int], k: int)</span> -&gt; int:</span>
        key, ans, count = <span class="hljs-number">1</span>, <span class="hljs-number">0</span>, list()
    
        <span class="hljs-keyword">for</span> num <span class="hljs-keyword">in</span> nums:
            <span class="hljs-keyword">if</span> num%<span class="hljs-number">2</span> == <span class="hljs-number">0</span>:
                key += <span class="hljs-number">1</span>
            <span class="hljs-keyword">else</span>:
                count.append(key)
                key = <span class="hljs-number">1</span>
        count.append(key)
        
        <span class="hljs-keyword">if</span> k &gt; len(count):
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>

        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(len(count)-k):
            ans += count[i]*count[i+k]
        
        <span class="hljs-keyword">return</span> ans
</div></code></pre>

    </body>
    </html>